/**
 * 开发者   : Marco
 * 创建时间 : 2016年12月15日, 下午2:45
 */

#include "array.h"

#include <stdlib.h>
#include <string.h>

#include "base.h"

namespace marco {
namespace node {

/* 实现类 */
class array_impl {
public:
    explicit array_impl(void) : capacity_(0), size_(0), members_(NULL) {}
    explicit array_impl(int capacity) : capacity_(capacity), size_(0) {
	members_ = (base**)malloc(capacity * sizeof(base*));
    }
    
    array_impl(array_impl& orig) : capacity_(orig.size_), size_(orig.size_) { // 拷贝构造, 不多预留空间, 与size一样大.
	if (capacity_) {
	    members_ = (base**)malloc(capacity_ * sizeof(base*));
	    memcpy(members_, orig.members_, capacity_*sizeof(base*));
	} else { members_ = NULL; } // 没有元素
    }
    
    ~array_impl(void) { free(members_); } // 析构, 并不delete各个成员元素指针.
    
    void reserve(int size) { // 预留空间
	if (capacity_ >= size) return; // 不比原来大
	capacity_ = size;
	members_ = (base**)realloc(members_, capacity_ * sizeof (base*));
    }
    
    void clear(void) { size_ = 0; } // 清空元素, 预留大小不会改变
    int size(void) const { return size_; } // 获取当前元素个数
    int capacity(void) const { return capacity_; } // 获取当前空间
    
    void push(base* member) { // 后置添加元素
	if (size_ >= capacity_) {
	    capacity_ += 10;
	    members_ = (base**)realloc(members_, capacity_ * sizeof (base*));
	}
	members_[size_++] = member;
    }
    
    void push(base** members, int count) { // 后置添加多个元素
	if (size_ + count >= capacity_) {
	    capacity_ += count + 5;
	    members_ = (base**)realloc(members_, capacity_ * sizeof (base*));
	}

	memcpy(members_+size_, members, count*sizeof(base*));
	size_ += count;
    }
    
    void push_sort(base** members, int count) { // 添加并排序
	push(members, count);
	sort(0, size_-1); // 排序
    }
 
#if 0
    void push_front(base* member) { // 前置添加元素
	if (size_ >= capacity_) {
	    capacity_ += 10;
	    members_ = (base**)realloc(members_, capacity_ * sizeof (base*));
	}
	
	if (size_) { // 之前有成员, 各后移
	    for (int i = size_; i != 0; --i) {
		members_[i] = members_[i-1];
	    }
	}
	
	members_[0] = member;
	size_ += 1;
    }
    
    base* pop_back(void) { // 从后取一个元素
	if (size_) {
	    size_ -= 1;
	    return members_[size_];
	}
	return NULL;
    }
    
    base* pop_front(void) { // 从前取一个元素
	if (size_) {
	    return members_[0];
	}
	
	return NULL;
    }
#endif
    
    int find_index(unsigned int id) { // 折半查找ID, 返回下标
	int mid, start = 0, end = size_ - 1;
	while (start <= end) {
	    mid = (start + end) / 2;
	    if (id == members_[mid]->get_id()) { return mid; } // 查找成功
	    if (id > members_[mid]->get_id()) { start = mid+1; } // 大还是小
	    else { end = mid - 1; }
	}
	return -1;
    }
    
    base* find_node(unsigned int id) { // 折半查找ID,返回节点
	int index;
	if ((index = find_index(id)) >= 0) { return members_[index]; }
    }
    
    void remove_index(int index) { // 删除指定下标的元素
	if (index < size_) { // 下标必须至少比元素个数小1
	    size_ -= 1;
	    for (int i = index; i < size_; ++i) // 后续元素依次前移
		members_[i] = members_[i+1];
	}
    }
    
    void remove_id(unsigned int id) { // 删除指定ID的元素
	int index;
	if ((index = find_index(id)) >= 0)
	    remove_index(index);
    }
    
    int remove_members(const base** members, int count) { // 删除多个成员
	int index, i, j;
	int remove_count = 0; // 实际要删除的个数
	int remove_index[count]; // 记录要删除的下标
	
	for (i = 0; i < count; ++i) {
	    if (members[i] && (index = find_index(members[i]->get_id())) >= 0) // 空指针忽略, ID未找到忽略
		remove_index[remove_count++] = index; // 记录要移除的下标
	}

	for (i = 0; i < remove_count; ++i) // 要移除的节点置为NULL
	    members_[remove_index[i]] = NULL;

	for (i = 0, j = 0; i < size_; ++i) { // 重新移位, 置为NULL的元素踢除
	    if (members_[i]) {
		members_[j++] = members_[i];
	    }
	}

	size_ -= remove_count;
	return remove_count; // 返回实际删除的个数
    }
    
    base** get_members_copy(int& total) { // 获取列表副本
	base** tmp;

	if (size_) {
	    int bytes = size_ * sizeof (base*); // 共复制的字节
	    tmp = (base**)malloc(bytes);
	    memcpy(tmp, members_, bytes);
	    total = size_;

	} else {
	    tmp = NULL;
	    total = 0;
	}

	return tmp;
    }
    
    base** get_members(void) { return members_; } // 获取成员列表, 危险

private:
    /**
    * 排序, 升序
    * @param start 起始下标
    * @param end 结束下标
    */
   void sort(int start, int end) {
       int mid = (start + end) / 2;
       if (start >= end) return;
       sort(start, mid);
       sort(mid + 1, end);
       merge_sort(start, mid, end);
   }

    /**
     * 执行归并排序
     * @param start 起始下标
     * @param mid 中间下标
     * @param end 结束下标
     */
    void merge_sort(int start, int mid, int end) {
	int len1 = mid - start + 1;
	int len2 = end - mid;
	base **left = (base**)malloc(len1 * sizeof(base*));
	base **right = (base**)malloc(len2 * sizeof(base*));

	if ((!left) || (!right)) { exit(EXIT_FAILURE); }

	int i = 0, j = 0, k = 0;
	for (i = 0; i < len1; i++) { left[i] = members_[start + i]; }
	for (j = 0; j < len2; j++) { right[j] = members_[j + mid + 1]; }
	i = j = 0;
	k = start;

	while (i < len1 && j < len2) {
	    if (left[i]->get_id() > right[j]->get_id()) { members_[k++] = right[j++]; }
	    else { members_[k++] = left[i++]; }
	}

	while (i < len1) { members_[k++] = left[i++]; }
	while (j < len2) { members_[k++] = right[j++]; }

	free(left);
	free(right);
    }
    
    int capacity_; // 内存容量
    int size_; // 当前大小
    base** members_; // 数据
};

array::array(void) {
}

array::~array(void) {
}

} // namespace node
} // namespace marco